/**
 * @program: 11.2
 * @description:
 * @author: 李鑫月
 * @create: 2021-11-02 19:01
 **/
class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}
public class MyLinkedList {
    public ListNode head;
    public void creatList(){
        ListNode listNode1=new ListNode(128);
        ListNode listNode2=new ListNode(127);
        ListNode listNode3=new ListNode(126);
        ListNode listNode4=new ListNode(125);
        ListNode listNode5=new ListNode(124);
        ListNode listNode6=new ListNode(123);


    }
    public void AddFirst(int data){
        ListNode node=new ListNode(data);
        if(this.head==null){
            head=node;
        }else {
            node.next=this.head;
            this.head=node;
        }

    }
    public void AddLast(int data){
        ListNode node=new ListNode(data);
        if(this.head==null){
            head=node;
        }else{
            ListNode cur=this.head;
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }



    }
    public int size(){
        ListNode cur=this.head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public boolean contains(int k){
        ListNode cur=this.head;
        while(cur!=null){
            if(cur.val==k){
                return true;
            }
            cur=cur.next;

        }
        return false;
    }
    public void display(){
        ListNode cur=this.head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    public void display2(ListNode h){
        ListNode cur=h;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    public ListNode findIndex(int index){
        ListNode cur=this.head;
        while ((index-1)!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        ListNode node=new ListNode(data);
        ListNode cur=this.head;
        ListNode pre=cur;
        if(index<0||index>=size()){
            return;
        }
        if(index==0){
            AddFirst(data);
        }else if(index==size()-1) {
            AddLast(data);
        }
        else {
//            for (int i = 0; i <index ; i++) {
//                pre=cur;
//                cur=cur.next;
//            }
            cur=findIndex(index);
            node.next=cur.next;
            cur.next=node;

        }

    }

    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if (this.head==null){
            System.out.println("空链表");
            return;
        }
        if(this.head.val==key){
            head=head.next;
            return;
        }
        ListNode cur=this.head;
        while(cur.next!=null){
            if(cur.next.val==key){
                cur.next=cur.next.next;
            }else {
                cur=cur.next;
            }
        }
        System.out.println("meiyouzhaodao");
    }

    //删除所有值为key的节点
    public ListNode removeAllKey(int key){
        ListNode cur=this.head.next;
        ListNode pre=this.head;
        if(this.head==null){
            System.out.println("空链表");
            return null;
        }
        while (cur!=null){
            if(cur.val==key){
                pre.next=cur.next;

                cur=cur.next;
            }else {
                pre=cur;
                cur=cur.next;
            }
            if(this.head.val==key){
                this.head=this.head.next;
            }
        }
        return this.head;

    }


    public void clear(){
        ListNode cur=this.head.next;
        if(this.head==null){
            return;
        }
        while(cur!=null){
            head=null;
            head=cur;
            cur=cur.next;

        }
        head=null;
    }
    public ListNode reverseList() {
        if(this.head==null){
            return null;
        }
//        if(this.head.next==null){
//            return this.head;
//        }

        ListNode cur=this.head.next;
        this.head.next=null;
        while(cur!=null){
            AddFirst(cur.val);
            cur=cur.next;
        }
        return this.head;
    }
    public ListNode reverseList2() {
        if(this.head==null){
            return null;
        }
    ListNode cur=this.head;
    ListNode prenh=null;
    while (cur!=null){
        ListNode curNext=cur.next;
        cur.next=prenh;
        prenh=cur;
        cur=curNext;
    }
    return prenh;
    }
    public ListNode reverseList3() {
        if(this.head == null) {
            return null;
        }
        ListNode cur = this.head;
        ListNode prev = null;

        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

}


